package com.sheng.leetcode.year2023.month08.day28;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author by ls
 * @date 2023/8/29
 * <p>
 * 57. 插入区间<p>
 * <p>
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。<p>
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。<p>
 * <p>
 * 示例 1：<p>
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]<p>
 * 输出：[[1,5],[6,9]]<p>
 * <p>
 * 示例 2：<p>
 * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]<p>
 * 输出：[[1,2],[3,10],[12,16]]<p>
 * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。<p>
 * <p>
 * 示例 3：<p>
 * 输入：intervals = [], newInterval = [5,7]<p>
 * 输出：[[5,7]]<p>
 * <p>
 * 示例 4：<p>
 * 输入：intervals = [[1,5]], newInterval = [2,3]<p>
 * 输出：[[1,5]]<p>
 * <p>
 * 示例 5：<p>
 * 输入：intervals = [[1,5]], newInterval = [2,7]<p>
 * 输出：[[1,7]]<p>
 * <p>
 * 提示：<p>
 * 0 <= intervals.length <= 10^4<p>
 * intervals[i].length == 2<p>
 * 0 <= intervals[i][0] <= intervals[i][1] <= 10^5<p>
 * intervals 根据 intervals[i][0] 按 升序 排列<p>
 * newInterval.length == 2<p>
 * 0 <= newInterval[0] <= newInterval[1] <= 10^5<p>
 */
public class LeetCode0057 {

    @Test
    public void test01() {
//        int[][] intervals = {{1, 3}, {6, 9}};
//        int[] newInterval = {2, 5};
        int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval = {4, 8};
//        int[][] intervals = {};
//        int[] newInterval = {5, 7};
//        int[][] intervals = {{1, 5}};
//        int[] newInterval = {2, 3};
//        int[][] intervals = {{}};
//        int[] newInterval = {2, 7};
        System.out.println(Arrays.deepToString(new Solution().insert(intervals, newInterval)));
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<List<Integer>> lists = new ArrayList<>();
        int start = newInterval[0], end = newInterval[1];
        // 获取 start 和 end 在 intervals 中的区间范围
        boolean flag = false;
        for (int[] interval : intervals) {
            if (!flag) {
                if (interval[1] < start || interval[0] > end) {
                    // 不相交
                    lists.add(Arrays.asList(interval[0], interval[1]));
                } else {
                    // 相交
                    start = Math.min(start, interval[0]);
                    end = Math.max(end, interval[1]);
                }
            } else {
                lists.add(Arrays.asList(interval[0], interval[1]));
            }
        }
        if (!flag) {
            lists.add(Arrays.asList(start, end));
        }
        // 集合转化为二维数组
        int[][] array = lists.stream().map(list -> list.stream().mapToInt(i -> i).toArray()).toArray(int[][]::new);
        // 排序
        Arrays.sort(array, Comparator.comparingInt(a -> a[0]));
        return array;
    }
}
